In digital transmission systems, the accepted measure of quality is the error rate, i.e., the proportion of received bits that are different from those transmitted. While the error rate is affected by virtually all aspects of the system design, it is also possible to address it directly with the use of error correction. A substantial improvement in error rate due to error correction can ease requirements on other system features such as amplifiers, equalizers, and span lengths; or alternatively, it can extend the state of the art transmission performance in terms of bits per second.
Known error correction systems require the transmission of information in addition to the data, or "overhead" information, and some kind of calculation using the received data and overhead information to generate the corrected data. The factors that can be traded off one against another and still provide effective error correction are the additional bandwidth/time required for transmission; the amount of time needed to perform the calculations; and the complexity and cost of the equipment.
Where bandwidth/time is a very high priority consideration, such as, for example, in digital radio systems, the amount of overhead information must be kept to a minimum.
A very effective known error correcting system uses multi-level transmission, coding of the most sensitive bits of each transmitted symbol according to a block code such as a Hamming code and a maximum likelihood decoder. The Hamming code comprises a series of data bits followed by several check bits. The check bits reflect the parity of various combinations of data bits. A syndrome is derived for each coded data block by recalculating the check bits from the received data bits according to the Hamming code and comparing them with the received check bits by modulo-two addition. If the syndrome is not zero, the received code word comprising the received data bits and check bits is not valid. The maximum likelihood decoder considers all of the valid code words that might have been transmitted that, with the received code word, would produce the particular syndrome. It calculates the euclidean distance between each valid code word and the actual amplitudes of the received symbol sequence, and selects the closest as the corrected word. The problem is that for long codes with a relatively low overhead the number of different valid code words that could produce each syndrome becomes enormous.
The Chase decoder assumes a subset of valid code words that would produce each syndrome, and selects the closest. Known Chase algorithms however leave something to be desired. If only single symbol errors are considered, that is, valid code words that differ from the received code word in only one symbol, the over-all error correction is not very effective. When multiple symbol error patterns are considered, the amount of calculation rapidly expands to the point where it cannot be completed in real time on a high speed transmission system.
An object of this invention is an error correction system that can produce effective error correction with a high speed data throughput using very low overhead.